Date: Wed, 20 Nov 1996 21:43:46 GMT
Server: NCSA/1.5
Content-type: text/html

<HTML>
<HEAD><LINK REV="made" HREF="mailto:dm@cs.bu.edu">

<TITLE>Computer Science 305 -- Fall 1995 ( 3-Nov-1995)</TITLE>
<!-- Changed by: David Martin,  3-Nov-1995 -->


</HEAD>
<BODY>

<H1><!WA0><IMG SRC="http://cs-www.bu.edu/lib/pics/bu-logo.gif"><BR><!WA1><IMG SRC="http://cs-www.bu.edu/lib/pics/bu-label.gif">
<EM>Computer Science 305<BR>
Automata and Formal Languages</EM></H1>

<H3>Fall 1995 Syllabus</H3>

<HR>

<!WA2><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw6.ps">Click here for a postscript version of Homework 6.</A>
(Due Thursday, December 16---NO LATE HOMEWORKS ACCEPTED)<BR>
<!WA3><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw5.ps">Click here for a postscript version of Homework 5.</A>  (Due Tuesday, November 21)<BR>
<!WA4><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw4.ps">Click here for a postscript version of Homework 4.</A>  (Due Tuesday, November 14)<BR>
<!WA5><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw3.ps">Click here for a postscript version of Homework 3.</A><BR>
<!WA6><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw2.ps">Click here for a postscript version of Homework 2.</A><BR>
<!WA7><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw1.ps">Click here for a postscript version of Homework 1.</A>

<H2>Instructor</H2>

<B>David Martin</B><BR>
MCS 209 (second floor, in Graduate Student Lane)<BR>
353-3326 (my office)<BR>
353-8919 (department office; messages only)<BR>

Click here to send mail to <!WA8><A HREF="mailto:dm@cs.bu.edu">dm@cs.bu.edu</A>.

<H2>Office Hours</H2>

Monday, 2:00pm - 3:00pm<BR>
Tuesday, 2:00pm - 3:00pm<BR>
Thursday, 2:00pm - 3:00pm<BR>
Watch for additional or altered hours as the semester progresses.

<H2>Classroom and Meeting Times</H2>

Classes meet Tuesday and Thursday, 12:30pm - 2:00pm
(i.e., 12:30pm - 1:50pm, according to  standard BU conventions)
in MCS B23, the basement of 111 Cummington St.

<H2>Required Textbook</H2>

<EM>Automata and Formal Languages: An Introduction,</EM>
Dean Kelley, Prentice Hall, 1995
 <P>

<H3>Other Useful Books</H3>

<UL>
<LI> <EM>Elements of the Theory of Computation,</EM>
Lewis & Papadimitriou, Prentice Hall, 1981


<LI> <EM>Introduction to Automata Theory, Languages, and Computation,</EM>
Hopcroft & Ullman, Addison-Wesley, 1979
</UL>


<H2>Prerequisites</H2>

To enroll in this course, you must have satisified the following course
requirements.  If you haven't done so but still want to remain in the
course, please see me.

<UL>
<LI> MA 293 (Discrete Mathematics 1).

<LI> CS 112 or CS 113 (Programming &amp; Data Structures in C).
</UL>



<H2>Topics</H2>
This course is a core requirement in undergraduate computer science
curriculums at most colleges.  Its purpose is threefold; first, to
encourage you to investigate the nature of computation; second, to further
develop your formal reasoning and writing skills; and third, to add new
techniques to your programming bag of tricks. <P>

Accordingly, we will develop several formal models of computation, each
more powerful than the last.  At each stage we will prove some of what our
intuition suggests (and sometimes, what it denies) about these models.  We
will also see how most models admit two very different characterizations:
one of machines that are able to recognize certain events, and another of
grammars that are able to generate exactly what these machines recognize.  <P>

In particular, we will study regular languages, regular expressions, finite
deterministic and nondeterministic automata, context-free grammars,
pushdown automata, turing machines --- and more, if time allows. <P>

<H2>Grading</H2>

<PRE>
6 Homeworks    60%
Midterm        20%     Thursday, October 19
Final          20%     Saturday, December 16, 12:30-2:30pm
</PRE>

Note that each test is worth 2 homeworks.  The tests will be much simpler
than the homeworks. <P>


<H2>Homework Assignments</H2>

When writing up your homework, there are two goals you must keep in mind:
first, to give evidence that you have put real thought into the problem,
and second, to convince the reader that your solution is correct <EM>and
that you know why</EM>.  As a programmer, you have some experience with
this sort of writing: an effective program must be written for both a
compiler and a human reader.  Similarly, solutions to your problems must be
correct in the sense of solving the stated problem, but they must also be
comprehensible to the grader. <P>

As with any writing, the first draft of a problem solution is usually
unpresentable.  All of the pieces may be there, but they tend to be
chaotically assembled.  <EM>The single most important thing you can do</EM>
to make your solutions presentable is to rewrite them after you have
discovered why they are correct, and then to throw away (or at least tuck
away) your initial draft.  Remember, scratch paper is cheap. <P>

Be careful to realize that this emphasis on presentation has nothing to do
with whether English is your native language or whether you prefer to write
your solutions with pencil, pen, quill, or word processor. 
  A well-written solution starts by stating assumptions and then
works towards a clearly defined goal, emphasizing the overall direction and
omitting the superfluous. <P>

<H2>Late Policy</H2>

In general, you will have at least one week to work on a homework
assignment and at least three opportunities to attend my office hours
before that assignment is due.  <P>


Assignments turned in late for any reason will be marked late and will be
scored at 60% of their face value.  Assignments turned in more than a week
after they were due will be scored at 0% of their face value --- that is, we
will still attempt to evaluate them, but they will not count towards your
grade.  For "excused" lateness, such as illness and family emergency, see
the "Grading Appeals" section below. <P>

<H2>Collaboration and Plagiarism</H2>

<PRE>
col.lab.o.rate \k*-'lab-*-.ra-t\ \-.lab-*-'ra--sh*n\ \-'lab-*-.ra-t-iv\ 
   \-.ra-t-*r\ vi [LL collaboratus, pp. of collaborare to labor together, fr. 
   L com- + laborare to labor] 1: to work jointly with others esp. in an 
   intellectual endeavor 2: to cooperate with or assist usu. willingly an 
   enemy of one's country and esp. an occupying force 3: to cooperate with an 
   agency or instrumentality with which one is not immediately connected - 
   col.lab.o.ra.tion n
</PRE>

Collaboration is encouraged (primarily in the first and third senses) when
working on homework problems and preparing for exams.  None of the problems
in this class are intended to have secret solutions; the more resourceful
you are at discovering solutions, the more time you will have to write them
well.  Indeed, if you are stuck on a problem, I will be happy to talk with
you about it during office hours.  However, the solutions you turn in must
be your original writing.  Copying a prepared solution is not collaboration
at all; it is plagiarism. <P>

<PRE>
pla.gia.rize \'pla--j*-.ri-z also -je--*-\ vt : to steal and pass off as 
   one's own (the ideas or words of another) to present as one's own an idea 
   or product derived from an existing source - pla.gia.riz.er n
</PRE>

Plagiarizing another's words is not tolerated at Boston University.  It is
so disdained that there are specific procedures for accusing and punishing
those who plagiarize.  Do not copy another person's work and present it as
your own. <P>

(The above definitions were snatched from the Webster server at BU.) <P>


<H2>Grading Appeals</H2>
<EM>Simple clerical errors</EM> will be corrected as soon as they
are brought to my attention. <P>


Perhaps you will disagree about the grading of a particular problem
or feel that an instance of lateness was justified.  In order to bring this
to my attention, you must prepare a written appeal with supporting
documents and give it to me during the last week of class.  I will
carefully consider these appeals and make reasonable adjustments to your
benefit when preparing the final grades.  <P>

This is <EM>only</EM> a mechanism for dealing with my gradebook in a fair
manner.  <EM>You are always welcome to approach me with your
concerns.</EM><P> 

If you don't know whether or how to write an appeal,
use this as a guideline: I am likely to look more kindly upon "That was
just a really bad week for me" than "My homework was always late because
I... uh... had a headache." <P> 


<H2>Attendance</H2>

Attendance is not an official part of the course grade, but it is your
responsibility to stay informed.  Some announcements will be made only in
class. <P>


<H2>Mailing List</H2>

Other announcements will be made only by email.  To add yourself to the
course mailing list, log on to a CS cluster computer (such as csa) and type <P>

<PRE>
    csmail -a cs305
</PRE>

<!WA9><IMG SRC=http://ei.cs.vt.edu/~history/ABC.GIF>
 <P>

The <!WA10><A HREF="http://www.cs.iastate.edu/cgi-bin/hit-count?jva/jva-archive.html">
Atanasoff-Berry Computer (ABC)</A>
 of 1939, claimed to be the first electronic digital computer.  Photo
courtesy of the 
<!WA11><A HREF="http://ei.cs.vt.edu/~history/">History of Computing Page</A> at
Virginia Tech. 

<HR>

Prepared by <!WA12><A
HREF="http://cs-www.bu.edu/students/grads/dm/Home.html">David Martin</A>.  Click
<!WA13><A HREF="http://cs-www.bu.edu/courses/Home.html"> here</A> for information on other courses.
</BODY>
</HTML>
